package com.zklh.leetcode.structure.monotonestack;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 下一个更大元素算法实现
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/7/25 17:02
 */
public class NextGreaterElements {

    public int[] nextGreaterElements(int[] nums) {
        // 存储结果
        int[] result = new int[nums.length];
        // 存储nums[i] 后所有元素的压缩结果, 去掉波谷, 只保留波峰节点
        LinkedList<Integer> stack = new LinkedList<>();

        for (int i = nums.length-1; i >= 0; i--) {

            // 先根据nums[i] 作为stack的顶层元素, 把stack压缩, 压缩原则就是去掉波谷, 保留波峰
            while (!stack.isEmpty() && stack.getFirst() <= nums[i]) {
                stack.removeFirst();
            }

            // 当前i 是否有挡板取决于当前 的stack 情况, 只要有剩余节点, 就是有挡板的
            result[i] = stack.isEmpty() ? -1 : stack.getFirst();
            // 将当前节点作为stack顶层
            stack.addFirst(nums[i]);
        }

        return result;

    }

    public static void main(String[] args) {
        NextGreaterElements nextGreaterElements = new NextGreaterElements();
        System.out.println(Arrays.toString(nextGreaterElements.nextGreaterElements(new int[]{2,1,2,4,3})));
    }

}
